Search for: All records

A set of high dimensional points X ={x1,x2,…,xn}⊆Rd in isotropic position is said to be δ -anti concentrated if for every direction v, the fraction of points in X satisfying |⟨xi,v⟩|⩽δ is at most O(δ). Motivated by applications to list-decodable learning and clustering, three recent works [7], [44], [71] considered the problem of constructing efficient certificates of anti-concentration in the average case, when the set of points X corresponds to samples from a Gaussian distribution. Their certificates played a crucial role in several subsequent works in algorithmic robust statistics on list-decodable learning and settling the robust learnability of arbitrary Gaussian mixtures. Unlike related efficient certificates of concentration properties that are known for wide class of distri-butions [52], the aforementioned approach has been limited only to rotationally invariant distributions (and their affine transformations) with the only prominent example being Gaussian distributions. This work presents a new (and arguably the most natural) formulation for anti- concentration. Using this formulation, we give quasi-polynomial time verifiable sum-of-squares certificates of anti-concentration that hold for a wide class of non-Gaussian distributions including anti-concentrated bounded product distributions and uniform distributions over Lp balls (and their affine transformations). Consequently, our method upgrades and extends results in algorithmic robust statistics e.g., list-decodable learning and clustering, to such distributions. As in the case of previous works, our certificates are also obtained via relaxations in the sum-of-squares hierarchy. However, the nature of our argument differs significantly from prior works that formulate anti-concentration as the non-negativity of an explicit polynomial. Our argument constructs a canonical integer program for anti-concentration and analysis a SoS relaxation of it, independent of the intended application. The explicit polynomials appearing in prior works can be seen as specific dual certificates to this program. From a technical standpoint, unlike existing works that explicitly construct sum-of-squares certificates, our argument relies on duality and analyzes a pseudo-expectation on large subsets of the input points that take a small value in some direction. Our analysis uses the method of polynomial reweightings to reduce the problem to analyzing only analytically dense or sparse directions. 

We develop new techniques for proving lower bounds on the least singular value of random matrices with limited randomness. The matrices we consider have entries that are given by polynomials of a few underlying base random variables. This setting captures a core technical challenge for obtaining smoothed analysis guarantees in many algorithmic settings. Least singular value bounds often involve showing strong anti-concentration inequalities that are intricate and much less understood compared to concentration (or large deviation) bounds. First, we introduce a general technique for proving anti-concentration that uses well-conditionedness properties of the Jacobian of a polynomial map, and show how to combine this with a hierarchical net argument to prove least singular value bounds. Our second tool is a new statement about least singular values to reason about higher-order lifts of smoothed matrices and the action of linear operators on them. Apart from getting simpler proofs of existing smoothed analysis results, we use these tools to now handle more general families of random matrices. This allows us to produce smoothed analysis guarantees in several previously open settings. These new settings include smoothed analysis guarantees for power sum decompositions and certifying robust entanglement of subspaces, where prior work could only establish least singular value bounds for fully random instances or only show non-robust genericity guarantees. 

We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph G = (V, E). The buffered expansion of a set S ⊆ V with a buffer B ⊆ V∖S is the edge expansion of S after removing all the edges from set S to its buffer B. An ε-buffered k-partitioning is a partitioning of a graph into disjoint components P_i and buffers B_i, in which the size of buffer B_i for P_i is small relative to the size of P_i: |B_i| ≤ ε|P_i|. The buffered expansion of a buffered partition is the maximum of buffered expansions of the k sets P_i with buffers B_i. Let h^{k,ε}_G be the buffered expansion of the optimal ε-buffered k-partitioning, then for every δ>0, h^{k,ε}_G ≤ O(1)⋅(log k) ⋅λ_{⌊(1+δ)k⌋} / ε, where λ_{⌊(1+δ)k⌋} is the ⌊(1+δ)k⌋-th smallest eigenvalue of the normalized Laplacian of G. Our inequality is constructive and avoids the ``square-root loss'' that is present in the standard Cheeger inequalities (even for k=2). We also provide a complementary lower bound, and a novel generalization to the setting with arbitrary vertex weights and edge costs. Moreover our result implies and generalizes the standard higher-order Cheeger inequalities and another recent Cheeger-type inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion. 

We prove a new generalization of the higher-order Cheeger inequality for partitioning with buffers. Consider a graph G=(V,E). The buffered expansion of a set S⊆V with a buffer B⊆V∖S is the edge expansion of S after removing all the edges from set S to its buffer B. An ε-buffered k-partitioning is a partitioning of a graph into disjoint components Pi and buffers Bi, in which the size of buffer Bi for Pi is small relative to the size of Pi: |Bi|≤ε|Pi|. The buffered expansion of a buffered partition is the maximum of buffered expansions of the k sets Pi with buffers Bi. Let hk,εG be the buffered expansion of the optimal ε-buffered k-partitioning, then for every δ>0, hk,εG≤Oδ(1)⋅(logkε)⋅λ⌊(1+δ)k⌋, where λ⌊(1+δ)k⌋ is the ⌊(1+δ)k⌋-th smallest eigenvalue of the normalized Laplacian of G. Our inequality is constructive and avoids the ``square-root loss'' that is present in the standard Cheeger inequalities (even for k=2). We also provide a complementary lower bound, and a novel generalization to the setting with arbitrary vertex weights and edge costs. Moreover our result implies and generalizes the standard higher-order Cheeger inequalities and another recent Cheeger-type inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion.